// DeflaterEngine.cs
//
// Copyright (C) 2001 Mike Krueger
// Copyright (C) 2004 John Reilly
// Copyright (C) 2010 Thomas Maierhofer
//
// (2010) This Code was modified from SharpZipLib http://www.icsharpcode.net/OpenSource/SharpZipLib/  
// to fit the needs of Second WAF - a heavy load web application framework 
//
// This file was translated from java, it was part of the GNU Classpath
// Copyright (C) 2001 Free Software Foundation, Inc.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//
// Linking this library statically or dynamically with other modules is
// making a combined work based on this library.  Thus, the terms and
// conditions of the GNU General Public License cover the whole
// combination.
// 
// As a special exception, the copyright holders of this library give you
// permission to link this library with independent modules to produce an
// executable, regardless of the license terms of these independent
// modules, and to copy and distribute the resulting executable under
// terms of your choice, provided that you also meet, for each linked
// independent module, the terms and conditions of the license of that
// module.  An independent module is a module which is not derived from
// or based on this library.  If you modify this library, you may extend
// this exception to your version of the library, but you are not
// obligated to do so.  If you do not wish to do so, delete this
// exception statement from your version.

namespace WAF.Content
{
    using System;
    using System.Diagnostics;

    // DEFLATE ALGORITHM:
    // 
    // The uncompressed stream is inserted into the window array.  When
    // the window array is full the first half is thrown away and the
    // second half is copied to the beginning.
    //
    // The head array is a hash table.  Three characters build a hash value
    // and they the value points to the corresponding index in window of 
    // the last string with this hash.  The prev array implements a
    // linked list of matches with the same hash: prev[index & WMASK] points
    // to the previous index with the same hash.
    // 


    /// <summary>
    /// Low level compression engine for deflate algorithm which uses a 32K sliding window
    /// with secondary compression from Huffman/Shannon-Fano codes.
    /// </summary>
    public partial class Deflater 
    {
        #region Constants
        const int TooFar = 4096;
        #endregion

        void UpdateHash()
        {
            hashIndexInserted = (window[windowStart] << HASH_SHIFT) ^ window[windowStart + 1];
        }


        int InsertPatternHash()
        {
            ushort previousHash;
            int hash = ((hashIndexInserted << HASH_SHIFT) ^ window[windowStart + (MIN_MATCH - 1)]) & HASH_MASK;
            previousHash = patternHashtable[hash];
            previousPattern[windowStart & WMASK] = previousHash;
            patternHashtable[hash] = unchecked((ushort)windowStart);
            hashIndexInserted = hash;
            return previousHash & 0xffff;
        }

        void SlideWindow()
        {
            Array.Copy(window, WSIZE, window, 0, WSIZE);
            matchStart -= WSIZE;
            windowStart -= WSIZE;
            blockStart -= WSIZE;


            checksumAdler32S1 %= 65521;
            checksumAdler32S2 %= 65521;

            // Slide the hash table (could be avoided with 32 bit values
            // at the expense of memory usage).
            for (int i = 0; i < HASH_SIZE; ++i)
            {
                int m = patternHashtable[i] & 0xffff;
                patternHashtable[i] = (ushort)(m >= WSIZE ? (m - WSIZE) : 0);
            }

            // Slide the prev table.
            for (int i = 0; i < WSIZE; i++)
            {
                int m = previousPattern[i] & 0xffff;
                previousPattern[i] = (ushort)(m >= WSIZE ? (m - WSIZE) : 0);
            }
        }

        /// <summary>
        /// Find the best (longest) string in the window matching the 
        /// string starting at strstart.
        ///
        /// Preconditions:
        /// <code>
        /// strstart + MAX_MATCH &lt;= window.length.</code>
        /// </summary>
        /// <param name="curMatch"></param>
        /// <returns>True if a match greater than the minimum length is found</returns>
        bool FindLongestMatch(int curMatch)
        {
            int chainLength = this.max_chain;
            int niceLength = this.niceLength;
            ushort[] prev = this.previousPattern;
            int scan = this.windowStart;
            int match;
            int best_end = this.windowStart + this.matchLen;
            int best_len = Math.Max(this.matchLen, MIN_MATCH - 1);

            int limit = Math.Max(this.windowStart - MAX_DIST, 0);

            int strend = windowStart + MAX_MATCH - 1;
            byte scan_end1 = this.window[best_end - 1];
            byte scan_end = this.window[best_end];

            // Do not waste too much time if we already have a good match:
            if (best_len >= this.goodMatchLength)
            {
                chainLength >>= 2;
            }

            /* Do not look for matches beyond the end of the input. This is necessary
            * to make deflate deterministic.
            */
            if (niceLength > windowLookahead)
            {
                niceLength = windowLookahead;
            }

            Debug.Assert(windowStart <= 2 * WSIZE - MIN_LOOKAHEAD, "need lookahed");

            do
            {


                Debug.Assert(curMatch < windowStart, "Current Match is in the lookahed, not in the block");

                if (window[curMatch + best_len] != scan_end ||
                 window[curMatch + best_len - 1] != scan_end1 ||
                 window[curMatch] != window[scan] ||
                 window[curMatch + 1] != window[scan + 1])
                {
                    continue;
                }

                match = curMatch + 2;
                scan += 2;

                /* We check for insufficient lookahead only every 8th comparison;
                * the 256th check will be made at strstart + 258.
                */
                while (
                    window[++scan] == window[++match] &&
                    window[++scan] == window[++match] &&
                    window[++scan] == window[++match] &&
                    window[++scan] == window[++match] &&
                    window[++scan] == window[++match] &&
                    window[++scan] == window[++match] &&
                    window[++scan] == window[++match] &&
                    window[++scan] == window[++match] &&
                    (scan < strend))
                {
                    // Do nothing
                }

                if (scan > best_end)
                {
                    Debug.Assert(hashIndexInserted != 0, "Found match: " + curMatch + "-" + (scan - windowStart));

                    matchStart = curMatch;
                    best_end = scan;
                    best_len = scan - windowStart;

                    if (best_len >= niceLength)
                        break;

                    scan_end1 = window[best_end - 1];
                    scan_end = window[best_end];
                }
                scan = windowStart;
            } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit && --chainLength != 0);

            matchLen = Math.Min(best_len, windowLookahead);
            return matchLen >= MIN_MATCH;
        }

        /*
        bool DeflateStoredXX(bool finish)
        {
            throw new NotSupportedException();

            if (!finish && (windowLookahead == 0))
            {
                return false;
            }

            windowStart += windowLookahead;
            windowLookahead = 0;

            int storedLength = windowStart - blockStart;

            if ((storedLength >= DeflaterConstants.MAX_BLOCK_SIZE) || // Block is full
                (blockStart < WSIZE && storedLength >= MAX_DIST) ||  // Block may move out of window
                finish)
            {
                bool lastBlock = finish;
                if (storedLength > DeflaterConstants.MAX_BLOCK_SIZE)
                {
                    storedLength = DeflaterConstants.MAX_BLOCK_SIZE;
                    lastBlock = false;
                }

                Debug.WriteLine("storedBlock[" + storedLength + "," + lastBlock + "]");
                FlushStoredBlock(blockStart, storedLength, lastBlock);
                blockStart += storedLength;
                return !lastBlock;
            }
            return true;
        }
        */

        void Compress(int length)
        {
            switch (this.dataFormat)
            {
                case DeflaterConfig.StreamFormat.GZIP:
                    int endIndex = windowStart + windowLookahead;
                    int windowIndex = endIndex - length;
                    while (windowIndex < endIndex)
                    {
                        unchecked
                        {
                            crc32 = CrcTable[(crc32 ^ window[windowIndex]) & 0xFF] ^ (crc32 >> 8);
                        }
                        ++windowIndex;
                    }
                    unchecked { originalSize += (uint)length; }
                    break;

                case DeflaterConfig.StreamFormat.ZLIB:
                    endIndex = windowStart + windowLookahead;
                    windowIndex = endIndex - length;
                    while (windowIndex < endIndex)
                    {
                        unchecked
                        {
                            checksumAdler32S1 += window[windowIndex];
                            checksumAdler32S2 += checksumAdler32S1;
                        }
                        ++windowIndex;
                    }
                    break;
            }


            if (windowLookahead >= MIN_MATCH) UpdateHash();

            if (this.fastCompression) while (DeflateOptimizedSpeed(false)) { }
            else while (DeflateOptimizedSize(false)) { };

        }


        bool DeflateOptimizedSpeed(bool finish)
        {
            if (windowLookahead < MIN_LOOKAHEAD && !finish)
                return false;

            while (windowLookahead >= MIN_LOOKAHEAD || finish)
            {
                if (windowLookahead == 0)
                {
                    // We are flushing everything
                    FlushBlock(blockStart, windowStart - blockStart, finish);
                    blockStart = windowStart;
                    return false;
                }

                if (windowStart > 2 * WSIZE - MIN_LOOKAHEAD)
                {
                    /* slide window, as FindLongestMatch needs this.
                     * This should only happen when flushing and the window
                     * is almost full.
                     */
                    SlideWindow();
                }

                int hashHead;

                if (windowLookahead >= MIN_MATCH && // We need 3 bytes to hash (MIN_MATCH) 
                    (hashHead = InsertPatternHash()) != 0 &&  // Pattern hash has been seen before
                    windowStart - hashHead <= MAX_DIST &&  // previos Hash is not out of reach  
                    FindLongestMatch(hashHead))
                {
                    // longestMatch sets matchStart and matchLen
                    bool full = AddDistance(windowStart - matchStart, matchLen);

                    windowLookahead -= matchLen;
                    if (matchLen <= max_lazy && windowLookahead >= MIN_MATCH)
                    {
                        while (--matchLen > 0)
                        {
                            ++windowStart;
                            InsertPatternHash();
                        }
                        ++windowStart;
                    }
                    else
                    {
                        windowStart += matchLen;
                        if (windowLookahead >= MIN_MATCH - 1)
                        {
                            UpdateHash();
                        }
                    }
                    matchLen = MIN_MATCH - 1;
                    if (!full)
                    {
                        continue;
                    }
                }
                else
                {
                    // No match found
                    AddLiteral(window[windowStart] & 0xff);
                    ++windowStart;
                    --windowLookahead;
                }

                if (IsFull())
                {
                    bool lastBlock = finish && (windowLookahead == 0);
                    FlushBlock(blockStart, windowStart - blockStart, lastBlock);
                    blockStart = windowStart;
                    return !lastBlock;
                }
            }
            return true;
        }


        /// <summary>
        /// Deflate optimized for best compression (in cost of speed)
        /// </summary>
        /// <param name="finish">if set to <c>true</c> [finish].</param>
        /// <returns>if progress was made true, else false </returns>
        /// <remarks></remarks>
        bool DeflateOptimizedSize(bool finish)
        {
            Debug.Assert(windowLookahead >= MIN_LOOKAHEAD || finish); 

            while (windowLookahead >= MIN_LOOKAHEAD || finish)
            {
                // All input is processed, and we exit (this is the last block)
                if (windowLookahead == 0)
                {
                    Debug.Assert(finish, "Only the last Block can exit this way");

                    // Differnt to DeflateFast
                    if (previousByteAvailable)
                    {
                        AddLiteral(window[windowStart - 1] & 0xff);
                    }
                    previousByteAvailable = false;

                    FlushBlock(blockStart, windowStart - blockStart, finish);
                    blockStart = windowStart;
                    return false; // no lookahead, block is finished  
                }

                // Slide the window so we don't get out the range of ushort for FindLongestMatch
                if (windowStart >= 2 * WSIZE - MIN_LOOKAHEAD)
                {
                    SlideWindow();
                }

                int prevMatch = matchStart;
                int prevLen = matchLen;
                if (windowLookahead >= MIN_MATCH)
                {

                    int hashHead = InsertPatternHash();

                    if ( hashHead != 0 &&
                        windowStart - hashHead <= MAX_DIST &&
                        FindLongestMatch(hashHead))
                    {

                        // longestMatch sets matchStart and matchLen

                        // Discard match if too small and too far away
                        if (matchLen == MIN_MATCH && windowStart - matchStart > TooFar)
                        {
                            matchLen = MIN_MATCH - 1;
                        }
                    }
                }

                // previous match was better
                if ((prevLen >= MIN_MATCH) && (matchLen <= prevLen))
                {
                    AddDistance(windowStart - 1 - prevMatch, prevLen);
                    prevLen -= 2;
                    do
                    {
                        windowStart++;
                        windowLookahead--;
                        if (windowLookahead >= MIN_MATCH)
                        {
                            InsertPatternHash();
                        }
                    } while (--prevLen > 0);

                    windowStart++;
                    windowLookahead--;
                    previousByteAvailable = false;
                    matchLen = MIN_MATCH - 1;
                }
                else
                {
                    if (previousByteAvailable)
                    {
                        AddLiteral(window[windowStart - 1] & 0xff);
                    }
                    previousByteAvailable = true;
                    windowStart++;
                    windowLookahead--;
                }

                if (IsFull())
                {
                    int len = windowStart - blockStart;
                    if (previousByteAvailable)
                    {
                        len--;
                    }
                    bool lastBlock = (finish && (windowLookahead == 0) && !previousByteAvailable);
                    FlushBlock(blockStart, len, lastBlock);
                    blockStart += len;
                    return !lastBlock;
                }
            }
            return true;
        }

        /// <summary>
        /// Hash index of string to be inserted
        /// (window[windowStart] << HASH_SHIFT) ^ window[windowStart + 1];
        /// </summary>
        int hashIndexInserted;

        /// <summary>
        /// Hashtable, hashing three characters to an index for window, so
        /// that window[index]..window[index+2] have this hash code.  
        /// Note that the array should really be unsigned short, so you need
        /// to and the values with 0xffff.
        /// ((hashIndexInserted << HASH_SHIFT) ^ window[windowStart + (MIN_MATCH -1)]) & HASH_MASK;
        /// ((window[windowStart] << HASH_SHIFT) ^ window[windowStart + 1]) << HASH_SHIFT) ^ window[windowStart + 2]) & HASH_MASK;
        /// </summary>
        ushort[] patternHashtable;

        /// <summary>
        /// <code>prev[index &amp; WMASK]</code> points to the previous index that has the
        /// same hash code as the string starting at index.  This way 
        /// entries with the same hash code are in a linked list.
        /// Note that the array should really be unsigned short, so you need
        /// to and the values with 0xffff.
        /// </summary>
        ushort[] previousPattern;

        // Begin of the current (best) match
        int matchStart;

        // Length of the current (best) match
        int matchLen;

        // Set if previous byte exists
        // this is an unstored literal
        bool previousByteAvailable;

        // Start of the current Block blockStart <= windowStart
        
        int blockStart;

        /// <summary>
        /// Points to the current byte (currently compressed) in the window.
        /// previous bytes are already compressed 
        /// next bytes build the lookahead where matches can be found
        /// </summary>
        int windowStart;

        /// <summary>
        /// lookahead is the number of bytes in the window starting at windowStart that are valid and not already compressed
        /// The algorithm uses this as lookahed buffer to do comparisons with previous matches
        /// So window[windowStart] until window[windowStart+windowLookahead-1] are valid bytes
        /// </summary>
        int windowLookahead;

        /// <summary>
        /// This array contains the part of the uncompressed stream that 
        /// is of relevance.  The current byte is indexed by windowStart.
        /// </summary>
        byte[] window;

        // DeflateStrategy strategy;

        int max_chain; 
        int max_lazy; 
        int niceLength;

        // Length of a good match to shorten the search for a good match
        int goodMatchLength;

        /// <summary>
        /// The current compression function.
        /// </summary>
        // int compressionFunction;

        // Use the algorithms and settings optimized for speed
        bool fastCompression;

        // Format of the Output Stream (RFC 1950 ZLIB, 1951 DEFLATE, 1952 GZIP )
        DeflaterConfig.StreamFormat dataFormat;

        

        ulong checksumAdler32S1; // Checksum for RFC 1950 / ZLIB Streams
        ulong checksumAdler32S2; // Checksum for RFC 1950 / ZLIB Streams

        uint crc32; // Checksum for RFC 1952 / GZIP Streams
        uint originalSize; // // Checksum for RFC 1952 / GZIP Streams
    }
}
